class UF:  # union find
    def __init__(self, n=10):
        self.n = n
        self.f = [0] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = i

    def find(self, x):
        if x == self.f[x]:
            return x
        else:
            return self.find(self.f[x])

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        self.f[fy] = fx

    def count(self):
        tot = 0
        for i in range(1, n + 1):
            if self.f[i] == i:
                tot += 1

        return tot


# 4
# 0 2 4 0
# 2 0 3 5
# 4 3 0 1
# 0 5 1 0
inf = 99999
n = 4
D = [[0, 2, 4, inf], [2, 0, 3, 5], [4, 3, 0, 1], [inf, 5, 1, 0]]
print(D)
edges = []
for x in range(n):
    for y in range(n):
        edges.append((x + 1, y + 1, D[x][y]))
edges.sort(key=lambda t: t[2])
print(edges)
uf = UF(n)
tot = 0
for edge in edges:
    x, y, t = edge
    if uf.find(x) != uf.find(y):
        tot += t
        uf.union(x, y)
print(tot)
